Search Results

Documents authored by de Vos, Tijn

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.61
Faster Cut Sparsification of Weighted Graphs

Authors: Sebastian Forster and Tijn de Vos

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
A cut sparsifier is a reweighted subgraph that maintains the weights of the cuts of the original graph up to a multiplicative factor of (1±ε). This paper considers computing cut sparsifiers of weighted graphs of size O(nlog (n)/ε²). Our algorithm computes such a sparsifier in time O(m⋅min(α(n)log(m/n),log (n))), both for graphs with polynomially bounded and unbounded integer weights, where α(⋅) is the functional inverse of Ackermann’s function. This improves upon the state of the art by Benczúr and Karger (SICOMP 2015), which takes O(mlog² (n)) time. For unbounded weights, this directly gives the best known result for cut sparsification. Together with preprocessing by an algorithm of Fung et al. (SICOMP 2019), this also gives the best known result for polynomially-weighted graphs. Consequently, this implies the fastest approximate min-cut algorithm, both for graphs with polynomial and unbounded weights. In particular, we show that it is possible to adapt the state of the art algorithm of Fung et al. for unweighted graphs to weighted graphs, by letting the partial maximum spanning forest (MSF) packing take the place of the Nagamochi-Ibaraki (NI) forest packing. MSF packings have previously been used by Abraham at al. (FOCS 2016) in the dynamic setting, and are defined as follows: an M-partial MSF packing of G is a set ℱ = {F₁, … , F_M}, where F_i is a maximum spanning forest in G⧵ ⋃_{j = 1}^{i-1}F_j. Our method for computing (a sufficient estimation of) the MSF packing is the bottleneck in the running time of our sparsification algorithm.
Cite as

Sebastian Forster and Tijn de Vos. Faster Cut Sparsification of Weighted Graphs. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 61:1-61:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{forster_et_al:LIPIcs.ICALP.2022.61,
  author =	{Forster, Sebastian and de Vos, Tijn},
  title =	{{Faster Cut Sparsification of Weighted Graphs}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{61:1--61:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.61},
  URN =		{urn:nbn:de:0030-drops-164029},
  doi =		{10.4230/LIPIcs.ICALP.2022.61},
  annote =	{Keywords: Cut Sparsification, Graph Algorithms}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2021.16
An Improved Random Shift Algorithm for Spanners and Low Diameter Decompositions

Authors: Sebastian Forster, Martin Grösbacher, and Tijn de Vos

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

Abstract
Spanners have been shown to be a powerful tool in graph algorithms. Many spanner constructions use a certain type of clustering at their core, where each cluster has small diameter and there are relatively few spanner edges between clusters. In this paper, we provide a clustering algorithm that, given k ≥ 2, can be used to compute a spanner of stretch 2k-1 and expected size O(n^{1+1/k}) in k rounds in the CONGEST model. This improves upon the state of the art (by Elkin, and Neiman [TALG'19]) by making the bounds on both running time and stretch independent of the random choices of the algorithm, whereas they only hold with high probability in previous results. Spanners are used in certain synchronizers, thus our improvement directly carries over to such synchronizers. Furthermore, for keeping the total number of inter-cluster edges small in low diameter decompositions, our clustering algorithm provides the following guarantees. Given β ∈ (0,1], we compute a low diameter decomposition with diameter bound O((log n)/β) such that each edge e ∈ E is an inter-cluster edge with probability at most β⋅ w(e) in O((log n)/β) rounds in the CONGEST model. Again, this improves upon the state of the art (by Miller, Peng, and Xu [SPAA'13]) by making the bounds on both running time and diameter independent of the random choices of the algorithm, whereas they only hold with high probability in previous results.
Cite as

Sebastian Forster, Martin Grösbacher, and Tijn de Vos. An Improved Random Shift Algorithm for Spanners and Low Diameter Decompositions. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{forster_et_al:LIPIcs.OPODIS.2021.16,
  author =	{Forster, Sebastian and Gr\"{o}sbacher, Martin and de Vos, Tijn},
  title =	{{An Improved Random Shift Algorithm for Spanners and Low Diameter Decompositions}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{16:1--16:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.16},
  URN =		{urn:nbn:de:0030-drops-157914},
  doi =		{10.4230/LIPIcs.OPODIS.2021.16},
  annote =	{Keywords: Spanner, low diameter decomposition, synchronizer, distributed graph algorithms}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact